// 工具函数
#include <sys/time.h>
#include "utils.h"
#include <termios.h>
#include <unistd.h>

//　修改终端的控制方式，1取消回显、确认　２获取数据　3还原
int getch(void)
{
    // 记录终端的配置信息
    struct termios old;
    // 获取终端的配置信息
    tcgetattr(STDIN_FILENO, &old);
    // 设置新的终端配置
    struct termios new = old;
    // 取消确认、回显
    new.c_lflag &= ~(ICANON | ECHO);
    // 设置终端配置信息
    tcsetattr(STDIN_FILENO, TCSANOW, &new);

    // 在新模式下获取数据
    int key_val = 0;
    do
    {
        key_val += getchar();
    } while (stdin->_IO_read_end - stdin->_IO_read_ptr);

    // 还原配置信息
    tcsetattr(STDIN_FILENO, TCSANOW, &old);
    return key_val;
}

long int new_id()
{
    struct timeval timestamp;
    gettimeofday(&timestamp, NULL);
    return timestamp.tv_usec;
}

void clear_stdin()
{
    stdin->_IO_read_ptr = stdin->_IO_read_end;
}

char *get_str(char *buffer, size_t length)
{
    if (buffer == NULL)
    {
        printf("空指针异常!!!\r\n");
        return NULL;
    }
    fgets(buffer, length, stdin);
    if (buffer[length - 1] == '\n')
    {
        buffer[length - 1] = '\0';
    }

    clear_stdin();

    return buffer;
}

char get_sex()
{
    printf("(男/M 女/W):");
    while (true)
    {
        char sex = getch();
        if (sex == 'w' || sex == 'm')
        {
            printf("用户输入性别：%s\r\n", sex == 'w' ? "女" : "男");
            return sex;
        }
    }
}

char get_cmd(char start, char end)
{
    while (true)
    {
        char val = getch();
        if (val >= start && val <= end)
        {
            return val;
        }
    }
}

char *get_pwd(char *passwd, bool showMask, size_t length)
{
    if (passwd == NULL)
    {
        return NULL;
    }

    size_t idx = 0;
    do
    {
        char val = getch();
        if (val == 127)
        { // 用户按了删除键
            if (idx > 0)
            {
                if (showMask)
                    printf("\b \b");
                idx--;
            }
            continue;
        }
        else if (val == 10)
        {
            printf("%d\r\n", val);
            break;
        }

        if (showMask)
            printf("*");
        passwd[idx++] = val;
    } while (length - 1 > idx);
    passwd[idx] = '\0';
    return passwd;
}

/*输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
*/
char *decodeString(const char *s)
{
    char strStack[65536];
    char buf[65536];
    int cntStack[1024], cntTop = 0, strTop = 0, pos = 0, cnt, bufSize;
    while (s[pos])
    {
        if (s[pos] > '0' && s[pos] <= '9')
        {
            cnt = 0;
            while (s[pos] >= '0' && s[pos] <= '9')
            {
                cnt = cnt * 10 + s[pos] - '0';
                pos++;
            }
            cntStack[cntTop++] = cnt;
        }
        else if (s[pos] == ']')
        {
            cnt = cntStack[--cntTop];
            bufSize = 0;
            while (strStack[--strTop] != '[')
            {
                buf[bufSize++] = strStack[strTop];
            }

            for (int i = 1; i <= cnt; i++)
            {
                for (int j = bufSize - 1; j >= 0; j--)
                {
                    strStack[strTop++] = buf[j];
                }
            }
            pos++;
        }
        else
        {
            strStack[strTop++] = s[pos];
            printf("%c", s[pos]);
            pos++;
        }
    }

    strStack[strTop++] = '\0';
    char *res = (char *)malloc(sizeof(char) * (strTop + 1));
    strcpy(res, strStack);
    return res;
}

// 二分法查找
// 参数：列表/长度/比较值
// 返回值：索引号
int dichotomy(void *arr[], int l, int r, int key)
{
    int mid = (l + r) / 2;
    while (l <= r)
    {
        if (key < *(int *)arr[mid])
        {
            l = mid + 1;
        }
        else if (key > *(int *)arr[mid])
        {
            r = mid - 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

// 快速排序
void _quick_sort(void *arr[], size_t left, size_t right, compare cmp)
{
    if (left >= right)
    {
        return;
    }

    size_t mid = (left + right) / 2;
    void *pv = arr[mid];
    size_t l = left, r = right;

    while (l < r)
    {
        while (l < mid && 1 != cmp(arr[l], pv))
            l++;
        if (l < mid)
        {
            arr[mid] = arr[l];
            mid = l;
        }

        while (mid < r && 1 != cmp(pv, arr[r]))
            r--;
        if (mid < r)
        {
            arr[mid] = arr[r];
            mid = r;
        }
    }

    arr[mid] = pv;
    if (mid - left > 1)
        _quick_sort(arr, left, mid - 1, cmp);
    if (right - mid > 1)
        _quick_sort(arr, mid + 1, right, cmp);
}

void quick_sort(void *arr[], size_t len, compare cmp)
{
    _quick_sort(arr, 0, len - 1, cmp);
}
